package PriorityQueue;

public class BigTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E top = (E)arr[0];
        arr[0] = arr[size - 1];
        size--;
        arr[size] = null;
        int i = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && (arr[i].priority() < arr[i * 2 + 1].priority() || arr[i].priority() < arr[i * 2 + 2].priority() ) ) {

            int j = 0;
            if (arr[i * 2 + 1].priority() > arr[i * 2 + 2].priority()) {
                j = i * 2 + 1;
            }else if (arr[i * 2 + 1].priority() <= arr[i * 2 + 2].priority()) {
                j = i * 2 + 2;
            }
            E temp = (E)arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = j;
        }
        return top;
    }

    public E poll1() {
        if (isEmpty()) {
            return null;
        }


        //交换头尾
        swap(0,size - 1);
        size--;
        //置为 null
        E ret = (E)arr[size];
        arr[size] = null;

        //下潜
        down(0);
        return ret;

    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if ( left < size && arr[max].priority() < arr[left].priority()) {
            max = left;
        }
        if (right < size && arr[max].priority() < arr[right].priority()) {
            max = right;
        }
        if (max != i) {
            swap(max,i);
            down(max);
        }
    }



    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E)arr[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}
